Wykład 10

Rozwiązywanie układów równań liniowych

Teoria

Dano macierz $A=[a_{ij}]\in {\sf M}_{m\times n} (\mathbb K)$. oraz wektor $b=(b_1, \ldots, b_m)\in \mathbb K^m.$ Układ

$$ \left\{ \begin{array}{ccccccccc} a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & = & b_1\\ \vdots & & \vdots & & & &\vdots & &\vdots\\ a_{m1}x_1 & + & a_{m2}x_2 & + & \cdots & + & a_{mn}x_n & = & b_m \end{array} \right. \tag{zapis skalarny, I} $$

nazywamy układem $m$ równań liniowych z $n$ niewiadomymi. Macierz $A$ to macierz współczynników układu; $b$ to wektor wyrazów wolnych.

Wektor $s=(s_1, \ldots, s_n)$ jest wektorem rozwiązań układu (I), albo krótko, rozwiązaniem, jeśli po podstawieniu $x_1=s_1, \ldots , x_n=s_n$ do równań układu otrzymamy równości.

Możemy także powiedzieć, że układ $x_1=s_1, \ldots , x_n=s_n$ jest rozwiązaniem układu (I).

Np.: Układ

$$\left\{ \begin{array}{ccccc} x & + & y & = & 2\\ x & - & y & = & 0 \end{array} \right. $$

jest układem dwu równań z dwiema niewiadomymi. Jego (jedynym) rozwiązaniem jest $x=1, y=1$;

natomiast układ

$$\left\{ \begin{array}{ccccc} x & + & y & = & 2\\ x & + & y & = & 0 \end{array} \right. $$

w ogóle nie ma rozwiązań. Mówimy, że jest sprzeczny.

Układ (I) możemy też zapisać następująco:

$$ x_1A^1+ \cdots + x_n A^n = b, \tag{zapis wektorowy, II} $$$$Ax=b. \tag{zapis macierzowy, III}$$

Niech $T_A\colon \mathbb K^n\to \mathbb K^m$ będzie zadane macierzą $A$, to znaczy, $T_A(u)=Au$ dla wszelkich $u\in \mathbb K^n$. Wtedy rozwiązać (I), to znaleźć takie $s\in \mathbb K^n$, że $T_A(s)=b$. Jeśli interesują nas wszystkie rozwiązania (I), to należy wyznaczyć $T_A^{-1}(b)$.

Następujące twierdzenie rozstrzyga kwestię, czy (I) ma rozwiązanie:

Twierdzenie 1. (Kronecker$-$Capelli) Układ (I) ma rozwiązanie (nie jest sprzeczny) wtedy i tylko wtedy, gdy

$$ \operatorname{rank} A= \operatorname{rank} [A^1, \ldots, A^n,b] = \operatorname{rank}[A,b] $$
(Rząd macierzy współczynników jest równy rzędowi macierzy rozszerzonej.)

Dowód. Układ (I) ma rozwiązanie lub, co na jedno wychodzi, (II) ma rozwiązanie wtedy i tylko wtedy, gdy $b\in \operatorname{lin}\{A^1, \ldots , A^n\}$ wtedy i tylko wtedy, gdy $\operatorname{rank} A=\operatorname{rank}[A,b]$. $\qquad\square$

Jeśli wektor wyrazów wolnych $b$ jest zerowy, to nasz układ, zapisany macierzowo, przyjmie postać:

$$ Ax=\mathbf 0. \tag{IIh} $$

Taki układ nazywamy jednorodnym. Jeśli $b\neq \mathbf 0$, to nasz układ jest niejednorodny.

Niech $V_0=\{x\in \mathbb K^n\colon Ax=\mathbf 0\}$. Oczywiście $V_0 = \operatorname{ker} T_A$, więc, na podstawie twierdzenia 3 wykład 6, $V_0$ jest podprzestrzenią liniową przestrzeni $\mathbb K^n$.

Niech teraz $x\in \mathbb K^n$. Przez $V_0+x$ oznaczmy zbiór

$$ V_0+x=\{v+x\colon v\in V_0\}. $$

($V_0+x$ jest przykładem podprzestrzeni afinicznej przestrzeni $\mathbb K^n$.)

Twierdzenie 2. Niech $s_0$ będzie pewnym rozwiązaniem układu równań (I) (równoważnie: równania $Ax=b$) oraz niech $V_0$ będzie podprzestrzenią złożoną ze wszystkich rozwiązań równania jednorodnego $Ax=\mathbf 0$. Wtedy zbiór wszystkich rozwiązań równania $Ax=b$ jest równy $V_0+s_0$.

Dowód. Jeśli $s$ jest rozwiązaniem naszego układu, to $As=b$. Połóżmy $x=s-s_0$. Wtedy

$$Ax= A(s-s_0)= As-As_0= b-b=\mathbf 0.$$

Stąd $x\in V_0$ i $s=x+s_0\in V_0+s_0$. W reultacie wszystkie rozwiązania układu (I) leżą w $V_0+s_0$.

Odwrotnie, przypuśćmy, że $s\in V_0+s_0$. Wtedy istnieje $x\in V_0$, że $s=x+s_0$. Ponadto,

$$ As=A(x+s_0)=Ax+As_0= 0+b=b $$

Stąd $s$ jest rozwiązaniem (I). $\square$

Każdą bazę $v^1, \ldots, v^k$ przestrzeni $V_0$ nazywamy fundamentalnym układem rozwiązań układu jednorodnego (IIh).

Twierdzenie 3. Niech $v^1, \ldots, v^k$ $-$ fundamentalny układ rozwiązań równania jednorodnego $Ax=0$ oraz niech niech $s_0$ $-$ jakiekolwiek rozwiązanie układu (I) (równoważnie: równania $Ax=b$). Wtedy $s$ jest rozwiązaniem układu (I) wtedy i tylko wtedy, gdy $s$ mozna zapisać w postaci:

$$ s=\lambda_1v^1 +\cdots+\lambda_kv^k +s_0, $$

$\lambda_1, \ldots, \lambda_k\in \mathbb K$.

Dowód. Wynika natychmiast z twierdzenia 2 i z faktu, że $v^1, \ldots, v^k$ stanowi bazę przestrzeni $V_0$. Stąd każdy $x$ należący do $V_0$ i tylko taki $x$ zapisuje się w postaci kombinacji liniowej $x=\lambda_1v^1 +\cdots +\lambda_kv^k$. $\square$.

Twierdzenie 4. Wymiar przestrzeni rozwiązań $V_0$ równania jednorodnego (IIh) wyraża się wzorem

$$ \dim V_0=n-\operatorname{rank} A. $$

Dowód. Na podstawie twierdzenia 3 wykład 6,

$$ \dim \operatorname{ker} T_A+\dim \operatorname{im} T_A =n. $$

Nadto $\dim V_0=\dim \operatorname{ker} T_A$ oraz na podstawie lematu 4 wykład 6, $\operatorname{rank} A=\dim \operatorname{im} T_A$. $\square$

Uwaga 1. Jeśli $m<n$, to $ \operatorname{rank} A\le m$, więc $\dim V_0>0$. W rezultacie, jeśli $Ax=b$ ma rozwiązanie, to wszystkich rozwiązań jest więcej. W przypadku, gdy ciało $\mathbb K$ ma nieskończenie wiele elementów, to i rozwiązań jest nieskończenie wiele (por. twierdzenie 3).

Przypomnijmy, że na podstawie twierdzenia 3 i uwagi 1 wykład 9, jeśli rząd macierzy kwadratowej rozmiaru $n\times n$ jest $n$, to jest ona odwracalna. Stąd mamy twierdzenie:

Twierdzenie 5. Jeśli $A\in {\sf M}_{n\times n}(\mathbb K)$, $\operatorname{rank} A=n$, to dla każdego wektora $b\in \mathbb K^n$ równanie macierzowe $Ax=b$ (równoważnie: układ (I)) ma dokładnie jedno rowiązanie $x=A^{-1}b$.

Dowód. Pomnóżmy lewostronnie obie strony równania $Ax=b$ przez $A^{-1}$. Otrzymamy $A^{-1}(Ax)=A^{-1}b$. Jednak mnożenie macierzy jest łączne, więc

$$ A^{-1}b= (A^{-1}A)x=Ix=x.\quad \square $$

Jeśli charakterystyka ciała $\mathbb K$ jest różna od $2$, to możemy skorzystać z twierdzenia 6 wykład 9, by wyrazić rozwiązanie "jawnym" wzorem:

$$ \left[\begin{array}{c} x_1 \\ \vdots \\ x_n\end{array}\right] = x=A^{-1}b = \left[ \begin{array}{ccc} \frac{D_{11}}{|A|} & \cdots &\frac{D_{1n}}{|A|}\\ \vdots & \ddots & \vdots\\ \frac{D_{n1}}{|A|} & \cdots &\frac{D_{nn}}{|A|} \end{array} \right] \left[\begin{array}{c} b_1 \\ \vdots \\ b_n\end{array}\right] = \left[\begin{array}{c} \frac{D_{11}}{|A|}b_1+\cdots +\frac{D_{1n}}{|A|}b_n \\ \vdots \\ \frac{D_{n1}}{|A|}b_1+\cdots +\frac{D_{nn}}{|A|}b_n\end{array}\right] $$

I otrzymaliśmy:

Twierdzenie 6. Niech $\chi(\mathbb K)\neq 2$. Jeśli $A\in {\sf M}_{n\times n}(\mathbb K)$ jest odwracalna, to równanie macierzowe $Ax=b$ (równoważnie: układ (I)) ma dokładnie jedno rozwiązanie dane wzorami Cramera:

$$ x_i=\frac{D_{i1}b_1+\cdots +D_{in}b_n}{|A|}= \frac{(-1)^{i+1}b_1|A_{1i}|+\cdots +(-1)^{i+n}b_n|A_{ni}|}{|A|}, $$

$i=1,\ldots, n$.

Uwaga 2. Twierdzenia 6 nie stosuje się do rozwiązywania układów równań. Ma ono jedynie znaczenie teoretyczne. W tym celu stosujemy metodę eliminacji zmiennych (w ograniczonym zakresie jest ona nauczana w szkole), nazywaną też metodą eliminacji Gaussa. Metoda ta pozwala na znalezienie rozwiązań, bądź wykazaniu, że ich nie ma także w przypadkach, gdy liczby równań i zmiennych są różne. Proszę o samodzielne zapoznanie się z tą metodą z podręcznika Kostrikina. Można także odnaleźć ją w jakimkolwiek innym podręczniku do algebry liniowej.

Wygodnym narzędziem do rozwiązywania układów równań liniowych jest pakiet sympy. Możemy go wywołać w notatniku jupyter. Rozwiążmy następujący przykład:

$$ \begin{array}{ccccccccccc} x_1 & - & 2x_2& + & 3x_3& - & x_4& -& 3x_5&= & 1\\ 2x_1 & + & x_2& + & x_3& + &2x_4& +& 2x_5&= & 7\\ -x_1 & + & 4x_2& + & 5x_3& - & x_4& -& 4x_5&= & 9\\ 3x_1 & - & 2x_2& + & 2x_3& + &3x_4& +& 2x_5&= & 9 \end{array} $$